/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/number-of-islands
   @Language: C++
   @Datetime: 20-01-06 14:44
   */

// DFS, Time O(mn), 8ms 98%; Space O(1), 10.4MB 99%
class Solution {
	void dfs(vector<vector<char> > &grid, int row, int col){
		const static int direct[][2]={{1,0}, {-1,0}, {0,1}, {0,-1}};
		const int m=grid.size(), n=grid[0].size();
		for(int i=0; i<4; ++i){
			const int r=row+direct[i][0], c=col+direct[i][1];
			if(r<0 || r>=m || c<0 || c>=n || grid[r][c]!='1') continue;
			grid[r][c]='0';
			dfs(grid, r, c);
		}
	}
public:
	int numIslands(vector<vector<char>>& grid) {
		int num=0;
		for(int i=0; i<grid.size(); ++i){
			for(int j=0; j<grid[0].size(); ++j){
				if(grid[i][j]!='1') continue;
				++num;
				dfs(grid, i, j);
			}
		}
		return num;
	}
};
